{"thread":{"id":"27042","subject":"Confused over packfile and index design","startedAt":"2011-04-08T23:58:41Z","lastAt":"2011-04-10T20:10:46Z","messageCount":7,"participants":["Steven E. Harris","Jeff King","Shawn Pearce","Nicolas Pitre"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"165469","messageId":"m2d3kw70su.fsf@Spindle.sehlabs.com","threadId":"27042","inReplyTo":null,"subject":"Confused over packfile and index design","fromName":"Steven E. Harris","fromEmail":"seh@panix.com","sentAt":"2011-04-08T23:58:41Z","receivedAt":"2011-04-08T23:58:41Z","isPatch":false,"sender":{"key":"seh@panix.com","avatar":"https://gravatar.com/avatar/d59ec0f7c010ee73cd67db381a5b865206fed17fd4278f12cdb6277db30033fc?d=mp&s=160"},"body":"I was reading the Git Book discussion¹ on the packfile and index formats,\nand there's a confusing set of assertions concerning the design choices\nthat sound contradictory.\n\nFirst, near the end of the section about the index format, we find the\nfollowing paragraph:\n\n,----\n| Importantly, packfile indexes are /not/ neccesary to extract objects\n| from a packfile, they are simply used to quickly retrieve individual\n| objects from a pack. The packfile format is used in upload-pack and\n| receieve-pack programs (push and fetch protocols) to transfer objects\n| and there is no index used then - it can be built after the fact by\n| scanning the packfile.\n`----\n\nThat suggests that it's possible to read the packfile linearly and\ndeduce where the various objects start and end, without the index\navailable.\n\nLater, in the section on the packfile format, we find this:\n\n,----\n| It is important to note that the size specified in the header data is\n| not the size of the data that actually follows, but the size of that\n| data /when expanded/. This is why the offsets in the packfile index are\n| so useful, otherwise you have to expand every object just to tell when\n| the next header starts.\n`----\n\nNow that makes it sound like without the index, even if one knows where\na packed object starts, reading its header tells its /inflated/ size,\n/not/ the number of remaining payload bytes representing the object. If\nthat's true, then how does one figure out where one object ends and the\nnext one begins /without the index/?\n\nRecall that the first paragraph quoted above says that the index can be\nbuilt from the packfile, as opposed to it being essential to reading the\npackfile. Is one of these paragraphs incorrect?\n\nThe Git documentation on the pack format² mentions that the packed\nobject headers represent the lengths as variable-sized integers\n\n,----\n| n-byte type and length (3-bit type, (n-1)*7+4-bit length)\n`----\n\nbut it doesn't say whether that's the number of (deflated) payload bytes\nor the inflated object size, as the Git Book asserts.\n\nI imagine that if the format is meant to record the size of the deflated\npayload, then it would be challenging to compress the data straight into\nthe packfile, because one wouldn't know the final size until it was\nwritten, which means that one wouldn't know how many bytes will be\nnecessary to write its length in the header, which means one wouldn't\nknow where to start writing the deflated payload.\n\nAre there any other clarifying documents you can recommend to understand\nthe design?\n\n\nFootnotes: \n¹ http://book.git-scm.com/7_the_packfile.html\n² http://www.kernel.org/pub/software/scm/git/docs/technical/pack-format.txt\n\n-- \nSteven E. Harris\n"},{"id":"165471","messageId":"20110409002047.GB7445@sigill.intra.peff.net","threadId":"27042","inReplyTo":"m2d3kw70su.fsf@Spindle.sehlabs.com","subject":"Re: Confused over packfile and index design","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-04-09T00:20:48Z","receivedAt":"2011-04-09T00:20:48Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Apr 08, 2011 at 07:58:41PM -0400, Steven E. Harris wrote:\n\n> ,----\n> | Importantly, packfile indexes are /not/ neccesary to extract objects\n> | from a packfile, they are simply used to quickly retrieve individual\n> | objects from a pack. The packfile format is used in upload-pack and\n> | receieve-pack programs (push and fetch protocols) to transfer objects\n> | and there is no index used then - it can be built after the fact by\n> | scanning the packfile.\n> `----\n> \n> That suggests that it's possible to read the packfile linearly and\n> deduce where the various objects start and end, without the index\n> available.\n\nYes. For example, when we do a \"git fetch\", we get _just_ the packfile\nand create our own local index.\n\n> Later, in the section on the packfile format, we find this:\n> \n> ,----\n> | It is important to note that the size specified in the header data is\n> | not the size of the data that actually follows, but the size of that\n> | data /when expanded/. This is why the offsets in the packfile index are\n> | so useful, otherwise you have to expand every object just to tell when\n> | the next header starts.\n> `----\n> \n> Now that makes it sound like without the index, even if one knows where\n> a packed object starts, reading its header tells its /inflated/ size,\n> /not/ the number of remaining payload bytes representing the object. If\n> that's true, then how does one figure out where one object ends and the\n> next one begins /without the index/?\n\nThe actual object data (whether it is the object itself or a delta) is\nall zlib-encoded, so it has its own size header and checksum there, I\nbelieve. The pack-format documentation is a bit vague, but a quick read\nof unpack_raw_entry and unpack_entry_data in builtin/index-pack.c seems\nto confirm that this is how it works.\n\nTake that response with a grain of salt, though. That is just from my\nquick read of the code, so I could be wrong.\n\n> Recall that the first paragraph quoted above says that the index can be\n> built from the packfile, as opposed to it being essential to reading the\n> packfile. Is one of these paragraphs incorrect?\n\nNo, if I'm correct, it is just that there is an extra header that\nneither mentions. :)\n\n> The Git documentation on the pack format² mentions that the packed\n> object headers represent the lengths as variable-sized integers\n> \n> ,----\n> | n-byte type and length (3-bit type, (n-1)*7+4-bit length)\n> `----\n> \n> but it doesn't say whether that's the number of (deflated) payload bytes\n> or the inflated object size, as the Git Book asserts.\n\nThat should be the inflated object size.\n\n> I imagine that if the format is meant to record the size of the deflated\n> payload, then it would be challenging to compress the data straight into\n> the packfile, because one wouldn't know the final size until it was\n> written, which means that one wouldn't know how many bytes will be\n> necessary to write its length in the header, which means one wouldn't\n> know where to start writing the deflated payload.\n\nI believe zlib handles streaming it out for us. I'm not too familiar\nwith zlib's format, but I assume it outputs in chunks with occasional\nheaders. So finding the end of stream means while reading through the\nwhole stream and skipping past each chunk.\n\n> Are there any other clarifying documents you can recommend to understand\n> the design?\n\nNot that I know of; what's in docs/technical is generally authoritative,\nexcept for reading the code.\n\n-Peff\n"},{"id":"165472","messageId":"BANLkTikXcvRf1bLJXFOHBcGcN-B0m_xSnw@mail.gmail.com","threadId":"27042","inReplyTo":"m2d3kw70su.fsf@Spindle.sehlabs.com","subject":"Re: Confused over packfile and index design","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-04-09T02:07:50Z","receivedAt":"2011-04-09T02:07:50Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Fri, Apr 8, 2011 at 19:58, Steven E. Harris <seh@panix.com> wrote:\n> I was reading the Git Book discussion¹ on the packfile and index formats,\n> and there's a confusing set of assertions concerning the design choices\n> that sound contradictory.\n\nIts not.\n\n> First, near the end of the section about the index format, we find the\n> following paragraph:\n>\n> ,----\n> | Importantly, packfile indexes are /not/ neccesary to extract objects\n> | from a packfile, they are simply used to quickly retrieve individual\n> | objects from a pack. The packfile format is used in upload-pack and\n> | receieve-pack programs (push and fetch protocols) to transfer objects\n> | and there is no index used then - it can be built after the fact by\n> | scanning the packfile.\n> `----\n>\n> That suggests that it's possible to read the packfile linearly and\n> deduce where the various objects start and end, without the index\n> available.\n\nIt is possible to do this.\n\nApplications can scan the pack file by reading the 12 byte fixed\nheader and getting the object count from the 2nd word. Then enter a\nloop that reads that many objects from the stream, before reading the\ntrailer SHA-1 checksum.\n\nTo read an object, the object header is consumed, reading the inflated\nlength from the variable length field. If the type code indicates the\nobject is a delta, the delta base reference is also read. Then\nremaining bytes are shoved into a libz inflate() routine until libz\nsays the stream is over. As Peff mentioned elsewhere in the thread,\nlibz maintains its own markers and checksum to know when the object's\nstream is over. As a safety measure, the inflated length from the\nobject header is checked against the number of bytes returned by libz.\nAny remaining data that libz didn't consume is the next object's\nheader and data.\n\n> Later, in the section on the packfile format, we find this:\n>\n> ,----\n> | It is important to note that the size specified in the header data is\n> | not the size of the data that actually follows, but the size of that\n> | data /when expanded/. This is why the offsets in the packfile index are\n> | so useful, otherwise you have to expand every object just to tell when\n> | the next header starts.\n> `----\n>\n> Now that makes it sound like without the index, even if one knows where\n> a packed object starts, reading its header tells its /inflated/ size,\n> /not/ the number of remaining payload bytes representing the object.\n\nYes.\n\n> I imagine that if the format is meant to record the size of the deflated\n> payload,\n\nIts not. Its meant to tell us how many bytes to malloc() in order to\nhold the result of the libz inflate() call when the object is being\nread from the packfile. That way we don't under or over allocate the\nresult buffer.\n\n-- \nShawn.\n"},{"id":"165487","messageId":"m28vvj7b0d.fsf@Spindle.sehlabs.com","threadId":"27042","inReplyTo":"BANLkTikXcvRf1bLJXFOHBcGcN-B0m_xSnw@mail.gmail.com","subject":"Re: Confused over packfile and index design","fromName":"Steven E. Harris","fromEmail":"seh@panix.com","sentAt":"2011-04-09T14:30:26Z","receivedAt":"2011-04-09T14:30:26Z","isPatch":false,"sender":{"key":"seh@panix.com","avatar":"https://gravatar.com/avatar/d59ec0f7c010ee73cd67db381a5b865206fed17fd4278f12cdb6277db30033fc?d=mp&s=160"},"body":"Shawn Pearce <spearce@spearce.org> writes:\n\n> Then remaining bytes are shoved into a libz inflate() routine until\n> libz says the stream is over. As Peff mentioned elsewhere in the\n> thread, libz maintains its own markers and checksum to know when the\n> object's stream is over.\n\nAh, so even though you as the caller don't know how much data to feed to\nlibz, so long as you continue feeding it until it signals completion, it\nwill figure it out and tell you how much data it needed after all.\n\n> As a safety measure, the inflated length from the object header is\n> checked against the number of bytes returned by libz.  Any remaining\n> data that libz didn't consume is the next object's header and data.\n\nI see. This means that it's the packed object's \"job\" -- or, rather, the\njob of the parser for the packed object -- to determine the payload\nlength. If the data was not compressed, then perhaps the deflated size\nindicated in the header could provide sufficient framing, but for now we\ndon't need to worry about such flexibility.\n\n[...]\n\n> Its meant to tell us how many bytes to malloc() in order to hold the\n> result of the libz inflate() call when the object is being read from\n> the packfile. That way we don't under or over allocate the result\n> buffer.\n\nDoes Git always inflate the objects into an in-memory buffer? As the\nsize of these objects can be very large (given the variable-length size\nencoding), is there any provision to inflate the object to a temporary\nfile?\n\n-- \nSteven E. Harris\n"},{"id":"165488","messageId":"BANLkTin8SXWC2cUqYvrPJrQWQKgMpRk4bg@mail.gmail.com","threadId":"27042","inReplyTo":"m28vvj7b0d.fsf@Spindle.sehlabs.com","subject":"Re: Confused over packfile and index design","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-04-09T14:45:41Z","receivedAt":"2011-04-09T14:45:41Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Sat, Apr 9, 2011 at 10:30, Steven E. Harris <seh@panix.com> wrote:\n> Shawn Pearce <spearce@spearce.org> writes:\n>> Its meant to tell us how many bytes to malloc() in order to hold the\n>> result of the libz inflate() call when the object is being read from\n>> the packfile. That way we don't under or over allocate the result\n>> buffer.\n>\n> Does Git always inflate the objects into an in-memory buffer?\n\nYes.\n\n> As the\n> size of these objects can be very large (given the variable-length size\n> encoding), is there any provision to inflate the object to a temporary\n> file?\n\nNot currently. If you don't have enough memory for the malloc() buffer\nof a big object, Git dies with an out of memory error.\n\n-- \nShawn.\n"},{"id":"165528","messageId":"alpine.LFD.2.00.1104092147520.28032@xanadu.home","threadId":"27042","inReplyTo":"m2d3kw70su.fsf@Spindle.sehlabs.com","subject":"Re: Confused over packfile and index design","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2011-04-10T02:08:53Z","receivedAt":"2011-04-10T02:08:53Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 8 Apr 2011, Steven E. Harris wrote:\n\n> I was reading the Git Book discussion¹ on the packfile and index formats,\n> and there's a confusing set of assertions concerning the design choices\n> that sound contradictory.\n> \n> First, near the end of the section about the index format, we find the\n> following paragraph:\n> \n> ,----\n> | Importantly, packfile indexes are /not/ neccesary to extract objects\n> | from a packfile, they are simply used to quickly retrieve individual\n> | objects from a pack. The packfile format is used in upload-pack and\n> | receieve-pack programs (push and fetch protocols) to transfer objects\n> | and there is no index used then - it can be built after the fact by\n> | scanning the packfile.\n> `----\n> \n> That suggests that it's possible to read the packfile linearly and\n> deduce where the various objects start and end, without the index\n> available.\n\nExact.\n\n> Later, in the section on the packfile format, we find this:\n> \n> ,----\n> | It is important to note that the size specified in the header data is\n> | not the size of the data that actually follows, but the size of that\n> | data /when expanded/. This is why the offsets in the packfile index are\n> | so useful, otherwise you have to expand every object just to tell when\n> | the next header starts.\n> `----\n> \n> Now that makes it sound like without the index, even if one knows where\n> a packed object starts, reading its header tells its /inflated/ size,\n> /not/ the number of remaining payload bytes representing the object. If\n> that's true, then how does one figure out where one object ends and the\n> next one begins /without the index/?\n\nThere is a reason why we use a pack index.  It is not essential to have \nit but it is extremely convenient.  Because to know exactly where one \nobject ends and therefore where the next one starts, we do have to \ninflate every object.  So the idea is to do that once to construct the \npack index and allow for random access once the index is available.  \nAccessing a particular object without the pack index would be extremely \ncostly otherwise, especially if it is towards the end of the pack.\n\nThe reason for storing only the expanded data size is to have the exact \nbuffer size allocated for the inflated data.  The zlib stream that \nfollows is encoded to consume only the needed data to produce the \ninflated object.  When the output buffer is all used, the zlib library \nshould flag the end of the deflated stream.  If not then there is an \nerror in the pack data.\n\n> Recall that the first paragraph quoted above says that the index can be\n> built from the packfile, as opposed to it being essential to reading the\n> packfile. Is one of these paragraphs incorrect?\n\nWell... in practice the index is pretty much essential if you want to \nread any random object from the pack.  But the index can be recreated \nat anytime simply by reading all objects sequentially from the pack.\n\n> The Git documentation on the pack format² mentions that the packed\n> object headers represent the lengths as variable-sized integers\n> \n> ,----\n> | n-byte type and length (3-bit type, (n-1)*7+4-bit length)\n> `----\n> \n> but it doesn't say whether that's the number of (deflated) payload bytes\n> or the inflated object size, as the Git Book asserts.\n\nIt is the inflated object size.\n\n> I imagine that if the format is meant to record the size of the deflated\n> payload, then it would be challenging to compress the data straight into\n> the packfile, because one wouldn't know the final size until it was\n> written, which means that one wouldn't know how many bytes will be\n> necessary to write its length in the header, which means one wouldn't\n> know where to start writing the deflated payload.\n\nExact.  And we also want to be able to construct a pack on the fly and \nstream it over a network connection without having to seek back.\n\n> Are there any other clarifying documents you can recommend to understand\n> the design?\n\nWhen in doubt, the code is always the ultimate source of information.\n\n\nNicolas\n"},{"id":"165578","messageId":"m24o657tq1.fsf@Spindle.sehlabs.com","threadId":"27042","inReplyTo":"alpine.LFD.2.00.1104092147520.28032@xanadu.home","subject":"Re: Confused over packfile and index design","fromName":"Steven E. Harris","fromEmail":"seh@panix.com","sentAt":"2011-04-10T20:10:46Z","receivedAt":"2011-04-10T20:10:46Z","isPatch":false,"sender":{"key":"seh@panix.com","avatar":"https://gravatar.com/avatar/d59ec0f7c010ee73cd67db381a5b865206fed17fd4278f12cdb6277db30033fc?d=mp&s=160"},"body":"Nicolas Pitre <nico@fluxnic.net> writes:\n\n> So the idea is to do that once to construct the pack index and allow\n> for random access once the index is available.  Accessing a particular\n> object without the pack index would be extremely costly otherwise,\n> especially if it is towards the end of the pack.\n\nThanks for the explanation. It's clear now.\n\n> The reason for storing only the expanded data size is to have the\n> exact buffer size allocated for the inflated data.  The zlib stream\n> that follows is encoded to consume only the needed data to produce the\n> inflated object.  When the output buffer is all used, the zlib library\n> should flag the end of the deflated stream.  If not then there is an\n> error in the pack data.\n\nThat provides some error checking, then, as we trust zlib to know when\nit's had enough input, and we have to trust its assessment on how much\nis enough, given the lack of delimiting or framing in the packfile\nformat.\n\nBy the way, I looked over the zlib manual¹, and I see that many of the\ninflating/decompressing functions require the caller to specify the\nnumber of input bytes available. There is inflateBack() that uses\ncallback functions to request more data upon underflow. The higher-level\ninflate() function also looks like it can be called in a loop, refilling\nthe input buffer upon underflow. Is Git using one of these two functions\nhere?\n\n[...]\n\n> When in doubt, the code is always the ultimate source of information.\n\nYes, I need to learn my way around in there to find the call sites\nrelevant to this discussion.\n\n\nFootnotes: \n¹ http://www.zlib.net/manual.html\n\n-- \nSteven E. Harris\n"}]}